from math import gcd
from tools_algorithm import *


# 2183. 统计可以被 K 整除的下标对数目
class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        ans = 0
        for num in nums:
            g = gcd(num, k)
            v = k // g
            ans += cnt[v]
            i = 1
            while i * i < num:
                if num % i == 0:
                    cnt[i] += 1
                    cnt[num // i] += 1
                i += 1
            if i * i == num:
                cnt[i] += 1
        return ans


class Solution:
    def countPairs(self, nums: List[int], k: int) -> int:
        cnt = Counter()
        ans = 0
        for num in nums:
            g = gcd(num, k)
            for i, v in cnt.items():
                if g * i % k == 0:
                    ans += v
            cnt[g] += 1
        return ans
